Marian Rejewski sinh ngày 16 tháng 8 năm 1905 ở Bromberg, thuộc tỉnh Posen của nước Phổ (nay là Bydgoszcz, Ba Lan).[9] Ông là con của Józef và Matylda, nhũ danh Thoms.[10] Sau khi học xong phổ thông, ông theo học ngành toán tại Học viện Toán học của Đại học Poznań, nằm trong Lâu đài Poznań.[11]

Năm 1929, ngay trước khi tốt nghiệp đại học, Rejewski đã bắt đầu tham gia một khóa học về mật mã học, khai giảng vào ngày 15 tháng 1,[12] do Cục Cơ yếu Bộ Tổng tham mưu Ba Lan tổ chức cho các sinh viên toán học nói tiếng Đức với sự giúp đỡ của Giáo sư Zdzisław Krygowski của Viện Toán học. Các buổi được diễn ra bên ngoài khuôn viên trường, trong một cơ sở quân sự[13] và, sau này Rejewski phát hiện ra ở Pháp vào năm 1939 rằng, "hoàn toàn dựa trên theo đúng nghĩa đen" cuốn sách xuất bản năm 1925 của Đại tá Pháp Marcel Givierge, Cours de cryptographie (Khóa học mật mã).[14] Rejewski và các bạn học gồm Henryk Zygalski và Jerzy Różycki là một trong số ít những người có thể bắt kịp với nội dung khóa học mà vẫn cân bằng với việc học tại trường như bình thường.[15]

Ngày 1 tháng 3 năm 1929, Rejewski tốt nghiệp với tấm bằng Thạc sĩ chuyên ngành Toán học.[16] Một vài tuần sau khi tốt nghiệp, lúc này ông vẫn chưa hoặc thành khóa học mật mã của Cục Cơ yếu, Rejewski tiếp tục theo học khóa học thống kê tính toán kéo dài hai năm tại Göttingen, Đức. Ông đã không hoàn thành khóa học này, bởi vì trong lúc ở nhà vào mùa hè năm 1930, ông đã nhận lời đề nghị từ Giáo sư Krygowski về việc trở thành trợ giảng toán học tại Đại học Poznań.[17] Ông cũng bắt đầu làm việc bán thời gian cho Cục Cơ yếu, lúc này đã thiết lập được một tiền đồn tại Poznań để giải mã các tin nhắn vô tuyến thu được từ quân đội Đức.[17] Rejewski làm việc khoảng mười hai giờ mỗi tuần trong một căn hầm dưới lòng đất gần Viện Toán học, thường được gọi vui là "Buồng đen".[18]

Cơ sở tại Poznań của Cục Cơ yếu bị giải thể vào mùa hè năm 1932. Vào ngày 1 tháng 9 năm 1932, tại Warsaw, Rejewski, Zygalski và Różycki đã gia nhập Cục Cơ yếu với tư cách là nhân viên dân sự làm việc tại tòa nhà Bộ Tổng tham mưu (Cung điện Saxon).[19] Nhiệm vụ đầu tiên của họ là giải một mật mã bốn ký tự đã bị mã hóa của Kriegsmarine (Hải quân Đức). Tiến độ giải mã ban đầu còn chậm, nhưng dần được đẩy nhanh sau khi nhóm thử nghiệm một thông tin thu được, bao gồm một tín hiệu sáu nhóm được truyền đi, theo sau đó là tín hiệu phản hồi có bốn nhóm. Các nhà mật mã học đã đoán chính xác tín hiệu đầu tiên là câu hỏi "Frederick Đại đế sinh năm nào?" và theo sau đó là câu trả lời "1712".[20]

Ngày 20 tháng 6 năm 1934, Rejewski kết hôn với Irena Maria Lewandowska, con gái của một nha sĩ khá giàu có. Họ có với nhau hai người con, một trai là Andrzej (Andrew), sinh năm 1936 và một gái tên là Janina (Joan), sinh năm 1939. Janina sau này cũng trở thành một nhà toán học giống như cha bà.[7]